1. Field of the Invention
The present invention is related to generalization in digital maps.
2. Description of the Related Art
Generalization in Maps
When a paper map is produced, shapes of objects represented in the map are rarely the same as they are in reality. For maps at anything other than the largest (most zoomed-in) scale, it is physically impossible to represent complex shapes like mountain roads exactly, because the width of the line describing the object is much too great to allow the true shape of the object to be illustrated. Cities, parks, and other areas may also have boundaries with complex shapes. Even when the line on a map is not too wide to allow a true representation of a shape, cartographers often smooth out a complex shape to make it more pleasing to a viewer's eye.
The simplification of objects represented on a map is called generalization. Generalization includes many kinds of operations: Complicated lines and boundaries may be smoothed out; narrow areas such as rivers may be represented as single lines; small areas such as small parks may be represented as single points; divided roads may be represented by single lines; highway interchanges may be represented by icons, often small white squares, instead of having their constituent roadways depicted; objects near roads may be displaced slightly from their true positions to improve visibility. All of these operations are forms of generalization. Our primary focus, however, is the first of these, namely, the simplification of lines. These lines can represent objects drawn one-dimensionally, such as roads, or the boundaries of two-dimensional objects, such as cities and parks.
Simplification as a Form of Generalization
In digital maps, one- and two-dimensional objects are typically represented as polylines or polygons. A polyline is a connected sequence of straight line segments. A polygon is a polyline that starts and ends at the same point. That is, if an object is actually curved in the real world, it is approximated by a sequence of points, called shape points, and the straight line segments connecting them. In the internal representation of the map, a one-dimensional object, or the one-dimensional boundary of a two-dimensional object, is typically represented by a list of its shape points. Because a polygon is merely a special case of a polyline, we frame the remaining discussion in terms of polylines for both increased readability and generality.
Often, in the use of digital map data the producer or user of the data finds that the data is much more precise, and the number of shape points is much greater, than is needed for the intended use. For example, this can happen when data originally collected for use at large (zoomed-in) scales is to be used instead at small (zoomed-out) scales. For example, digital road map data may be collected with enough shape points to guarantee that the polyline representing the road is never more than 20 meters from the actual road. When map data is to be used to draw a map of the entire United States on a computer screen, it typically suffices to make sure that the polyline is never more than, for example, five kilometers from the actual road. If the map is drawn using the more precise data, there are many times more points than necessary. This makes the data file much larger than necessary, and makes the processing time much longer than necessary as well.
Faced with this situation, the maker or user of digital map data often wants to generalize the polylines in a map so that they are not much more precise than the intended use requires. There are many possible ways to do this. In one method, each polyline is replaced by an entirely new polyline having new shape points, created in such a way that it does not deviate by more than a specified distance from the original polyline. In another method, each polyline is replaced by a new polyline with shape points selected from those of the original polyline in such a way that the new polyline does not deviate by more than a specified distance from the original polyline. That is, a subset of the shape points of the original polyline, in the order in which they occurred in the original polyline, is selected to be the shape points of the new polyline. This process is sometimes referred to as simplification of the original polyline. Because it has conventionally been thought advantageous for algorithmic reasons not to introduce new shape points, simplification is often a desirable method of generalizing polylines. However, simplification can be carried out in a variety of ways, and conventional methods have some significant drawbacks associated with them.
One of the most common methods of polyline simplification is the Douglas-Poiker algorithm (D. H. Douglas and T. K. Peucker, Algorithms for The Reduction of The Number of Points Required to Represent a Digitized Line or its Caricature, 10 Canadian Cartographer 112-22, 1973). In this method, a maximum deviation distance dmax is specified—for example, 5 km. The first and last shape points of the polyline are marked as “to be kept”. The chord (direct line segment) from the first shape point P1 to the last shape point Pn of the original polyline is considered. The shape points of the original polyline are inspected to see whether any of them are more than the maximum distance dmax from the chord. If any are, then the shape point Pi farthest from the chord is marked as “to be kept”, and the same operation is applied to the partial polylines from the beginning P1 to the farthest point Pi and from the farthest point Pi to the end point Pn. This process of checking, marking, and subdividing is applied recursively until the original polyline has been broken up into pieces such that the chord from the beginning to the end of each piece is no farther than the maximum deviation distance dmax from any of the shape points in between.
Another common algorithm is due to Lang (T. Lang, Rules For Robot Draughtsmen, 42 Geographical Magazine 50-51, 1969). In this method, a maximum number of points nmax to step, and a maximum deviation distance dmax, are specified. The algorithm then starts at the first point P1, which it marks as “to be kept”. It then considers the chords from P1 to Pi, where various values for i are tried, starting with i=1+nmax, then with i=nmax, then with i=nmax−1, then with i=nmax−2, and so on, until a chord is found that stays within distance dmax of the original polyline. Suppose that the first such chord is from P1 to Pc. The algorithm marks point Pc as “to be kept”, and then repeats the step of checking chords, from Pc to Pi, starting with i=c+nmax, then with i=c+nmax−1, then with i=c+nmax−2, and so on, until a chord is found that stays within distance dmax of the original polyline. The end point of the first such chord is marked as “to be kept”. This process is then repeated until the last shape point of the polyline is marked as “to be kept”.
There are other such common polyline simplification algorithms in use. The most commonly used algorithms, including those just discussed, share the property that the determination as to whether points are kept is based on properties of the intervening chords. However, since those chords are not considered in relation to other nearby chords, this can cause several problems when the resulting simplified polylines are used.
For example, without constraints on the angles formed by the resulting chords, the angles in the simplified polylines can be much sharper than in the original polyline. When the polylines are used for a purpose in which angles have significance, such as some driving-time estimating methods, the result can be significantly different from the original polyline, reducing the utility of the simplified polyline.
A more serious problem is that because the relationship of two chords that meet at a kept point is not constrained, the angle formed at the point can be reversed. For example, FIG. 1 illustrates a case in which an original polyline 102, which includes the shape points P1, P2, P3, P4, P5, P6, P7, P8, makes a sharp turn to the right at point P7, but the generalized polyline 104, which comprises the shape points P1, P7, P8, makes a sharp turn to the left at the same point P7. If the polyline is used to describe a driving route, this can be unfortunate, causing a driver to go in the wrong direction. If it is used as the boundary of an area, such as a park or lake, the result is even worse—such a change in angle can make the boundary of the area no longer topologically correct, turning the area inside-out, and making it impossible to draw the area correctly using the new polyline.
One advantage of generalization is that the smaller number of shape points makes the processing of the data faster at little or no cost to the accuracy of the data. Another advantage is that the smaller number of shape points makes the data file smaller, again at little or not cost to the accuracy of the data.
Some methods of representing data can use fewer bits for “rounder” coordinates. For example, in some methods of representing data, data is digitized to an accuracy of 2−28 revolution (about 1.34×10−6 degrees, which provides an accuracy of about 15 cm). Latitudes and longitudes measured to that accuracy can easily be represented in 27 and 28 bits, respectively. However, in some schemes of representing such data, a block of data all of which has n trailing zero bits can be represented with n fewer bits each. Thus, for example, if all the coordinates in a block of data all end with four zero bits when represented in units of 2−28 revolution, then latitudes and longitudes in that block of data can be represented using 23 and 24 bits respectively.